Range sum of BST [DFS]¶
Time: O(N); Space: O(H); medium
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary search tree is guaranteed to have unique values.
Example 1:
10
/ \
5 15
/ \ \
3 7 18
Input: root = {TreeNode} [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:
10
/ \
5 15
/ \ / \
3 7 13 18
/ /
1 6
Input: root = {TreeNode} [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
Notes:
The number of nodes in the tree is at most 10000.
The final answer is guaranteed to be less than 2^31.
[8]:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
1. Depth First Search¶
[9]:
class Solution1(object):
"""
Time: O(N)
Space: O(H)
"""
def rangeSumBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: int
"""
result = 0
s = [root]
while s:
node = s.pop()
if node:
if L <= node.val <= R:
result += node.val
if L < node.val:
s.append(node.left)
if node.val < R:
s.append(node.right)
return result
[10]:
s = Solution1()
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
L = 7
R = 15
assert s.rangeSumBST(root, L, R) == 32
L = 6
R = 10
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(13)
root.right.right = TreeNode(18)
root.left.left.left = TreeNode(1)
root.left.right.left = TreeNode(6)
L = 6
R = 10
assert s.rangeSumBST(root, L, R) == 23